home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2693 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: damage.usa1.net!news
  2. From: crb3@usa1.com (crb3@usa1.com)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: Mon, 22 Jan 1996 00:36:05 GMT
  6. Organization: USAinternet, Inc.
  7. Message-ID: <4dum0o$nsq@damage.usa1.net>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca> <4dpian$gij@oxy.rust.net> <4drjkc$il4@news.gate.net>
  9. NNTP-Posting-Host: wmn1-147.usa1.com
  10. X-Newsreader: Forte Free Agent 1.0.82
  11.  
  12. Quoth bhutto@gate.net (William Hutto):
  13.  
  14. >;
  15. >;Given some number, there is a neat trick to generate a mask which will
  16. >;have exactly one bit set in it.  The bit set will be the least
  17. >;significant non-zero bit in the original number:
  18. >;
  19. >;    mask = ~number & number;
  20.  
  21. >It's faster just to use:
  22.  
  23. >mask = 0;
  24.  
  25. >;
  26. >;Now, if number contained a single non-zero bit (and is therefore a
  27. >;power of 2),  mask will be equal to number.  Therefore:
  28. >;
  29. >;   if (number == (~number & number))
  30.  
  31. >    if(!number)
  32.  
  33. >;   {
  34. >;        /* number is a power of 2 */
  35.  
  36. >    /* number == 0 */
  37.  
  38. >;   }
  39. >;
  40.  
  41. >Bill
  42.  
  43. >"Whatcha got on?...Your mind?"
  44.  
  45. You're right, as shown it zeroes out, but take another look.
  46. The quoted neat trick is broken, but there is something there (I had
  47. to play it out on paper and HP16 to see for myself  :) ). It works if
  48. you use the unary-minus (2's-comp) operator rather than the bitwise
  49. negation (1's-comp) operator on the first RH arg:
  50.  
  51. if(  val == ( (-val) & val) )
  52.     return(TRUE);
  53.  
  54. Thanks for the neat trick btw
  55.  
  56. --cr
  57.  
  58.